The invention concerns a method of integer division or modular reduction secure against covert channel attacks, and in particular differential attacks. The invention can be used for performing division operations in a more general cryptographic method, for example a secret or public key cryptographic method. Such a cryptographic method can for example be implemented in electronic devices such as chip cards.
The security of cryptographic methods lies in their ability to keep concealed the confidential data or data derived from confidential data that they manipulate.
A malevolent user may possibly undertake attacks aimed as discovering in particular confidential data contained and manipulated in processing operations performed by the calculation device executing a cryptographic method.
Amongst the best known attacks, simple or differential covert channel attacks can be cited. Covert channel attack means an attack based on a physical quality measurable from outside the device and whose direct analysis (simple attack) or analysis according to a statistical method (differential attack) makes it possible to discover data manipulated in processing operations performed in the device. These attacks have in particular been disclosed by Paul Kocher (Advances in Cryptology—CRYPTO'99, vol. 1666 of Lecture Notes in Computer Science, pp. 388-397. Springer-Verlag, 1999).
Amongst the physical quantities that can be used for these purposes, the execution time, the current consumption, the electromagnetic field radiated by the part of the component used for executing the calculation, etc, can be cited. During the execution of a method, the manipulation of a bit, that is to say its processing by a particular instruction, leaves a particular imprint on the physical quantity in question, according to the value of this bit and/or according to the instruction. In other words, the trace (that is to say the change over time of the physical quantity in question) left by the component executing the method is different depending on whether a bit equal to one or a bit equal to zero is being manipulated. Covert channel attacks are based on this weakness of cryptographic methods.
The cryptographic methods using as a basic operation a modular exponentiation operation of the type Y=XD, X, Y and D being integer numbers, have been very widely studied during the past few years. By way of example, the RSA method, the key exchange according to Diffie-Hellman or the DSA signature method can be cited. Significant progress has been made in protecting these methods against covert channel attacks.
On the other hand, no study has been made on making secure cryptographic methods using as an elementary operation an integer division of the type q=a div b and r=a mod b, a and b being two operands, q and r being respectively the quotient and the remainder of the integer division of a by b. a and/or b are secret data, for example elements of a key of the method. For example, the method of Barrett (P. Barret, “Implementing the RSA public key encryption algorithm on a standard digital signal processing”, vol 263 of Lecture Notes in Computer Science, pp. 311-323, Springer Verlag, 1987), the method of Quisquater (U.S. Pat. No. 5,166,978, November 92) or the RSA method implemented according to the Chinese remainder theorem (J J Quisquater and C Couvreur, “Fast decipherment algorithm for RSA public key cryptosystem”, Electronics Letter, vol 18, 99. 905-907, October 1982) are cryptographic methods using an integer division as an elementary operation.
Such cryptographic methods using an integer division method and/or a modular reduction method are sensitive to covert channel attacks, as will be seen in the following example.
A known method for using both an integer division and a modular reduction is the so called “paper/pencil” method. This method in practice repeats the method used when such an operation is performed by hand. This method is set out below.
Given two data items a=(am−1, . . . , a0) of m bits and b=(bn−1, . . . , b0) of n bits, n less than or equal to m and bn−1 γ O, the so called “paper/pencil” division method calculates the quotient q=a div b and the remainder r=a div b. For this purpose, the method successively performs several division of an integer A of n+1 bits by the integer b of n bits. It is necessary in practice to have 0 [A/b <2, which is the case whenever bn−1 γ 0.
The remainder r is a number of no more than n bits since r<b. The quotient q for its part is a number of no more than m−n+1 bits since q=a div b [a div (bn−1*2n−1)=a div 2n−1=(am−1, . . . , an−1) since b μ bn−1*2n−1 and (am−1, . . . , an−1) is a number of m−n+1 bits. At the end of the division method, the quotient q is stored in the m−n+1 least significant bits of the register containing initially the number a. The most significant bit of the remainder r is stored in 1-bit register used as a carry during the calculation and the n−1 least significant bits of the remainder r are stored in the n−1 most significant bits of the register initially containing the number a.
As this work is carried out in base 2, the quotient bit of the integer division A div b has only two possible values: 0 or 1. Thus a simple way of performing the operation A div b consists of subtracting b from A and then testing the result: if the result of A−b is positive, then A div b=1, if the result of A−b is strictly negative, then A div b=0.
The complete division method can then be written in the following manner:                Input: a=(0, am−1, . . . , a0) b=(bn−1, . . . , b0)        Output: q=a div b and r=a mod b        A=(0, am−1, . . . , am−n+1)        For j=1 to (m−n+1), do:                    a <- SHLm−1(a, 1) ; σ <- carry            A <-SUBn(A, b) ; σ <- σ OR carry            if (σ=TRUE) then A <- ADDn(A, b) if not lsb(a)=1                        End For        